#include "stdafx.h"

#ifndef hash_table_h_included
#define hash_table_h_included

//#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define sizeofmember(TYPE, MEMBER) ((sizeof)((TYPE *)0)->MEMBER)

unsigned int simple_hash(const char *str, unsigned int len);

typedef struct tag_SINGLE_LIST
{
    //void * ptr_record;   // pointer to the record
    void * next;         // pointer to the next item of the single list
}SINGLE_LIST;

class CHashTable 
{
protected:
    long   prime;
    unsigned int (*hf)(const char *str, unsigned int len);
    int m_index_field_offset;
    int m_index_field_len;
    int m_record_len;
    long m_record_count;
    char * m_record_buf;    // lAssistCount: prime. hash_index as hash_no

    void** hash_map;    // array size : prime. 
    SINGLE_LIST* single_list; // array size : m_record_num
    char * m_str_index_field; // hash_index field for calc hash value 

public:

    /*****************************************/
    /* Contructor:                           */
    /* ------------------------------------- */
    /*                                       */
    /* record_num:    estimated size of table   */
    /* VoidPtr:    hash function             */
    /*                                       */
    /*****************************************/

    CHashTable(char * ptr, long record_count, int record_len, int index_field_offset, int index_field_len, unsigned int (*VoidPtr)(const char *str, unsigned int len) = simple_hash)
    {
        prime     = 0;
        hash_map = NULL;
        hf        = VoidPtr;

        long prime_table[20] = {1009L, 5009L, 10009L, 20011L, 50021L, 100003L, 200003L, 500009L, 1000003L,2000003L, 5000011L,10000019L,20000003L,50000017L,100000007L,200000033L,500000003L,1000000007L,2000000011L};
        //2147483648 -- max of long
        int hash_index = 0;
        while(hash_index < 20)
        {
            prime = prime_table[hash_index];
            if(record_count <= prime) break;
            hash_index++;
        }


        hash_map = new void*[prime];
        memset(hash_map, 0, sizeof(hash_map)*prime);
        single_list = new SINGLE_LIST [record_count];
        memset(single_list, 0, sizeof(SINGLE_LIST)*record_count);

        m_index_field_offset     = index_field_offset;
        m_index_field_len        = index_field_len   ;
        m_record_len             = record_len        ;
        m_record_count           = record_count;
        m_record_buf = ptr;

        m_str_index_field = new char [m_index_field_len + 4];

    };

    /*****************************************/
    /* Destructor:                           */
    /*****************************************/
    ~CHashTable()
    {
        delete[] single_list;
        delete[] hash_map;
        delete[] m_str_index_field;
    };

    /*****************************************/
    /* AddKey:                               */
    /* ------------------------------------- */
    /*                                       */
    /* key   :    hash key                   */
    /* member:    member pointer to store    */
    /*                                       */
    /*****************************************/
    BOOL AddKey(char *record, long record_idx)
    {
        if (!hash_map)  return(FALSE);
        if (!hf)         return(FALSE);
        if (record_idx > m_record_count)  return(FALSE);
        
        if (0 == *(record)) return(FALSE);

        long hash_index = hf(record + m_index_field_offset, m_index_field_len) % prime;
        //if((hash_index < 0) || (hash_index >= prime)) return(FALSE);
        
        void ** ptr_hash = hash_map + hash_index;
        SINGLE_LIST* plist = single_list + record_idx;
        if (NULL != plist->next)
        {
            // must be some error.
            return (FALSE);
        }
        if (NULL == *ptr_hash )
        {
            *ptr_hash = (void *)plist;
        }
        else
        {
            plist->next = *ptr_hash;
            *ptr_hash = (void *)plist;
        }

        return(TRUE);
    };

   BOOL AddTable()
   {
       long i;
       char *p;
       p = m_record_buf;
       for (i=0;i<m_record_count;i++)
       {
           AddKey(p, i);
           p += m_record_len;
       }
       return TRUE;
   }

   BOOL SaveToFile(FILE * fpmap, FILE * fplst)
   {
       fwrite(hash_map, sizeof(void *), prime,fpmap);
       fwrite(single_list, sizeof(SINGLE_LIST), m_record_count,fplst);
       return TRUE;
   }

   BOOL RestoreFromFile(FILE * fpmap, FILE * fplst)
   {
       fread(hash_map, sizeof(void *), prime,fpmap);
       fread(single_list, sizeof(SINGLE_LIST), m_record_count,fplst);
       return TRUE;
   }

   /*****************************************/
    /* RemoveKey:                            */
    /* ------------------------------------- */
    /*                                       */
    /* key     :  hash key                   */
    /* free_mem:  free allocated memory      */
    /*                                       */
    /*****************************************/
    BOOL RemoveKey(char *record)
    {
        if(!hash_map)  return(FALSE);
        if(!hf)         return(FALSE);
        if(prime <= 0)  return(FALSE);
        if(0 == *(record)) return(FALSE);

        long hash_index = hf(m_str_index_field, m_record_len);
        if((hash_index < 0) || (hash_index >= prime)) return(FALSE);

        return(FALSE);
    };


    /*****************************************/
    /* GetMember:                            */
    /* ------------------------------------- */
    /*                                       */
    /* key:       member key                 */
    /*                                       */
    /*****************************************/
    char * GetMember(char * index_field)
    {
        if(!hash_map)  return(NULL);
        if(!hf)         return(NULL);
        if(prime <= 0)  return(NULL);
        if(0 == *(index_field)) return(NULL);

        long hash_index = hf(index_field, m_index_field_len) % prime; 
        // if((hash_index < 0) || (hash_index >= prime)) return(NULL);

        SINGLE_LIST* plist = (SINGLE_LIST* ) (*(hash_map+hash_index));
        if(plist == NULL) return(NULL);

        do 
        {
            long idxtmp = ((long)plist - (long)single_list)/sizeof(SINGLE_LIST);
            char * ptr_record = m_record_buf + idxtmp*m_record_len ;
            if (0 == memcmp(index_field, ptr_record + m_index_field_offset, m_index_field_len))
            {
                return ptr_record ;
            }
            plist = (SINGLE_LIST* )(plist->next);
        } while (plist);

        return(NULL);
    };

};
#endif